package com.kevinkk.greedy;

import java.util.Arrays;

/**
 * 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
 * <p>
 * 注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
 */

public class NonOverlappingIntervals {
    class Solution {
        public int eraseOverlapIntervals(int[][] intervals) {
            int res = 0;
            Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));

            for (int i = 1; i < intervals.length; i++) {
                // 如果发生重叠，删除当前区间
                if (intervals[i][0] < intervals[i - 1][1]) {
                    res++;
                    intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);
                }
            }

            return res;
        }
    }
}
